/**
 * @author 徐楠
 * @date 2022/3/5 15:00
 * @version 1.0
 */

package com.xunan.likou;

import java.util.HashSet;
import java.util.Set;

public class MissingFirstPositiveNumber {
    public static void main(String[] args) {
        //int[] nums = {7, 8, 9, 11, 12};
        int[] nums = {3,4,-1,1};
        int result = firstMissingPositive1(nums);
        System.out.println(result);
        System.out.println("+++++++++++");
        int i = firstMissingPositive2(nums);
        System.out.println(i);
    }

    public static int firstMissingPositive1(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            set.add(nums[i]);
        }
        for (int i = 1; i <= nums.length; i++) {
            if (!set.contains(i)) {
                return i;
            }
        }
        return nums.length + 1;
    }

    /**
     * 思路
     * n个数中缺失的数只能是[1, n + 1]，因为缺n得先有1~n-1可以实现,缺n+1得先有1~n可以实现,但缺n+2得先有1~n+1不可能实现
     * 因此只需统计数组中包含的1~n即可，先缺的那个数字则是目标值，若都不缺则说明目标值是n+1
     * 统计的工作可以使用哈希表，但为了节省空间，可以将原数组设计成哈希表，即原地哈希，数字1对应下标0，数字2对应下标1，以此类推
     * 例如有数字1，则将下标0对应数字设为负数（为了防止干扰，将原数组负数设为n+1，n+1表示无效），表示数组有1
     * 设计成负数是为了不覆盖掉原来的值，仅起标记作用，之后若遍历到可以取绝对值获得原值
     * 超出n的数字则不需理会，因为我们只需统计1~n的数
     * 当所有数字都统计完，先为正的那个下标+1则是目标值（不为负说明该下标没有映射到），若都不为负则说明目标值是n+1（说明1~n都映射到了）
     *
     * @param nums
     * @return
     */
    public static int firstMissingPositive2(int[] nums) {
        int n = nums.length;
        System.out.println(n);
        System.out.println("----");
        for (int num : nums) {
            System.out.print(num + "  ");
        }
        System.out.println("----");
        // 1. 先处理数组中的负值，排除干扰
        for (int i = 0; i < n; i++) {
            if (nums[i] <= 0) {
                nums[i] = n + 1;
            }
        }
        System.out.println("----");
        for (int num : nums) {
            System.out.print(num + "  ");
        }
        System.out.println("----");
        // 2. 统计包含的1~n，在其映射的下标作标记（设为负数）
        for (int i = 0; i < n; i++) {
            int num = Math.abs(nums[i]);
            //上面一步把负数设置为大于num的正数，原数组中的正数设为负数，方便下面一步获取下标
            if (1 <= num && num <= n && nums[num - 1] > 0) {
                nums[num - 1] = -nums[num - 1];
            }
        }
        System.out.println("----");
        for (int num : nums) {
            System.out.print(num + "  ");
        }
        System.out.println("----");
        // 3. 获得目标值：获取第一步中负数下标离0下标最近的一个
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        return n + 1;
    }
}
